package com.lazycat.leetcode.editor.cn;
//2023-07-19 21:03:17
//递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。 
//
// 示例1: 
//
// 
// 输入：A = 1, B = 10
// 输出：10
// 
//
// 示例2: 
//
// 
// 输入：A = 3, B = 4
// 输出：12
// 
//
// 提示: 
//
// 
// 保证乘法范围不会溢出 
// 
//
// Related Topics 位运算 递归 数学 👍 94 👎 0

class RecursiveMulitplyLcci {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new RecursiveMulitplyLcci().new Solution();
        solution.multiply(3,4);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int multiply(int A, int B) {

        if(B == 1){
            return A;
        }
        //如果不为1进行奇偶验证。
        //奇数 (multiply(A,B>>1)<<1)+A    >>1等价于/2  <<1等价于*2
        //偶数 multiply(A,B>>1)<<1
        return (B&1) != 0 ? (multiply(A,B>>1)<<1)+A : multiply(A,B>>1)<<1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}